A content addressable memory (CAM) stores a plurality of keys, and when presented with a search key, outputs the location in the CAM of a stored key that matches the search key. Although CAMs have many applications, one such application is routing in a computer or communications network. FIG. 1 illustrates an example of a prior art CAM.
The CAM 100 of FIG. 1 includes a word memory 102, comparators 152, and a location decoder 172. W N-bit keys are stored in the memory 102, where W and N are integers. The memory 102 can also store an N-bit mask for each stored key. Such a mask can identify some bits of the corresponding stored key as “do not care” bits, meaning that those bits are to be deemed to match a corresponding bit of an inputted search key 116 regardless of the value of the corresponding search key bit. Each comparator 152 comprises a key bit input 122 and a search key bit input 142 and possibly also a mask bit input 132. The location decoder 172 is connected to outputs 162 of the comparators 152.
The CAM 100 identifies a location in the memory 102 of a stored key that matches an inputted search key 116 as follows. An address incrementor 176 provides an address 104 of a first location in the memory 102, which causes the memory 102 to output the N-bit key 106 stored at the first location in the memory 102. The memory 102 can also output an N-bit mask 108 associated with the key 106.
Corresponding individual bits of the outputted key 106, the outputted mask 108, and the search key 116 can be provided to each of the comparators 152. That is, the first bits of the outputted key 106, the outputted mask 108, and the search key 116 can be provided to the first comparator 152. If the first bit of the outputted mask 108 is active or if the first bits of the outputted key 106 and the search key 116 have the same value, the first comparator 152 indicates a match on its output 162. Similarly, the second through the Nth bits of the outputted key 106, the outputted mask 108, and the search key 116 are provided to the second through the Nth comparators 152 each of which provides an output 162 indicating whether the corresponding bit is masked by the outputted mask 108 or there is a match between the corresponding bits of the outputted key 106 and the search key 116. The location decoder 172 determines whether the outputs 162 from the comparators 152 indicate that the search key 116 matches the outputted key 106 subject to the outputted mask 108. If so, the location decoder 172 identifies at its output 174 the address 104 as the location of a key in the memory 102 that matches the search key 116.
Otherwise, the address incrementor 176 increments the address 104, causing the memory 102 to output 106 the key stored at the next address in the memory 102 and output 108 any associated mask. The comparators 152 and location decoder 172 then determine whether the new outputted key 106 from the next address 104 in the memory 102 matches the search key 116. The foregoing is repeated (the address incrementor 176 increments the address 104 and the comparators 152 and location decoder 172 determine whether the key 106 output from the new address 104 in the memory 102 matches the search key 116) until a key is found in the memory 102 that matches the search key 116 or the address incrementor 176 increments through all W of the addresses 104 of the memory 102 at which a key is stored.
The prior art CAM 100 of FIG. 1 can thus require as many as W cycles to identify a stored key in the memory 102 that matches a search key 116. Another drawback is that the prior art CAM 100 requires at least two or three (depending on whether a mask and thus the mask output 108 and bit inputs 132 are included in the CAM 100) inputs 122, 132, 142 to the comparators 152 for every bit of the search key 116. The CAM 100 thus requires 2N or 3N comparator inputs 122, 132, 142, where N is the number of bits in the search key 116 as noted above. Although other prior art CAM architectures are known, such other architectures also suffer from one or both of these shortcomings or different shortcomings. Embodiments of the present invention improve one or more of such shortcomings in prior art CAMs.